package main

import "fmt"

func main() {

}

//TreeNode 二叉树节点
type TreeNode struct {
	data       interface{}
	leftChild  *TreeNode
	rightChild *TreeNode
}

//createBinaryTree 创建二叉树
func createBinaryTree(inputDatas *LinkedArray) *TreeNode {
	if inputDatas == nil || inputDatas.GetSize() == 0 {
		return nil
	}
	var curNode *TreeNode
	//移除并获取链表中的第一个元素
	data, _ := inputDatas.Remove(0)
	if data != nil {
		curNode = &TreeNode{data: data}
		curNode.leftChild = createBinaryTree(inputDatas)
		curNode.rightChild = createBinaryTree(inputDatas)
	}

	return curNode
}

//PreOrderTraveral 前序遍历
//前序遍历：输出的顺序是 根左右
//先输出根节点内容，再输出子节点的左子节点，若左子节点依然存在其左子节点，则继续输出
//若某个节点无左子节点则输出其右子节点
//某个节点无左子节点也无右子节点，或者左右子节点都输出完了，则回到上级节点，输出其右子节点
//概括起来就是：先输出根节点，再输出左子节点，无左子节点输出右子节点
func PreOrderTraveral(node *TreeNode) {
	if node == nil {
		return
	}
	fmt.Println(node.data)
	PreOrderTraveral(node.leftChild)
	PreOrderTraveral(node.rightChild)
}

//InOrderTraveral 中序遍历
func InOrderTraveral(node *TreeNode) {
	if node == nil {
		return
	}
	InOrderTraveral(node.leftChild)
	fmt.Println(node.data)
	InOrderTraveral(node.rightChild)
}

//PostOrderTraveral 后序遍历
func PostOrderTraveral(node *TreeNode) {
	if node == nil {
		return
	}
	PostOrderTraveral(node.leftChild)
	PostOrderTraveral(node.rightChild)
	fmt.Println(node.data)
}

//levelOrderTraveral 层序遍历
func levelOrderTraveral(node *TreeNode) {
	queue := &Queue{}
	queue.Enqueue(node)
	for !queue.IsEmpty() {
		ele, _ := queue.Dequeue()
		curNode := ele.(*TreeNode)
		fmt.Println(curNode.data)
		if curNode.leftChild != nil {
			queue.Enqueue(curNode.leftChild)
		}

		if curNode.rightChild != nil {
			queue.Enqueue(curNode.rightChild)
		}

	}
}
